package Agent;

import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.*;
import Env.*;
/**
 * TODO Put here a description of what this class does.
 *
 * @author danny.
 *         Created 18/11/2011.
 */
public class GreedyAgent extends AbstractAgent {
	
	private Vector<Integer> path;
	private int positionInPath;
	
	
	public GreedyAgent (int start,int goal,Environment env) throws Exception{
		super(start,goal,env);
		positionInPath=0;
		distance = new int[env.getGraph().n+1];
		path=dijkstra(start,goal,env.getGraph());
		
	}
	
	
	

	final int[] distance ;
	/**
	 * TODO Put here a description of what this method does.
	 *
	 * @param start
	 * @param goal
	 * @param graph
	 * @param vertexes
	 * @return
	 * @throws Exception getEdgeCost
	 */
	private Vector<Integer> dijkstra(int start, int goal, Graph graph) throws Exception {
		
		boolean [] S= new boolean [graph.n+1];
		final int[] papa = new int[graph.n+1];
		
		PriorityQueue<Integer> Q= new PriorityQueue(graph.n,new Comparator<Integer>() {
		
		

			@Override
			public int compare(Integer o1, Integer o2) {
				return distance[o1]-distance[o2];
			}
		});
		
		for (int i=0;i<=graph.n+1;i++){
			if (i==start)
				distance[i]=0;
			else 
				distance[i]=Integer.MAX_VALUE;
			
			Q.add(i);
		}
		
		while (!Q.isEmpty()){
			int v=Q.poll();
			Vector<Integer> q= graph.getAllConnected(v);
			for (Integer i:q){
				if (!S[i]){
					int cost=graph.getEdgeCost(v,i);
					if (distance[i]>distance[v]+cost){
						distance[i]=distance[v]+cost;
						papa[i]=v;
					}
				}
			}
			S[v]=true;
			
		}
		
			
		
		
		
		
		
		return new Vector<Integer>( getPath(this.goal,papa));  
	}

	/**
	 * TODO Put here a description of what this method does.
	 *
	 * @param goal
	 * @param papa 
	 * @reurn
	 */
	private Collection<Integer> getPath(int goal, int[] papa) {
		Vector<Integer> ans = new Vector<Integer>();
		Vector<Integer> ans2 = new Vector<Integer>();
		Integer x=goal;
		while (x!=null){
			ans.add(x);
			x=papa[x];
		}
		
		for (int i=0;i<ans.size();i++)
			ans2.add(ans.elementAt(ans.size()-i));
		
		return ans2;
	}

	@Override
	protected void chooseCarAndVertex() throws Exception {
		
	}
	
	
	

}
